package dp;

import java.util.Arrays;

public class LongestCommonSubsequence1143 {
    public int longestCommonSubsequence(String t1, String t2) {
        int[][] dp = new int[t1.length()+1][t2.length()+1];
        for (int[] a: dp) {
            Arrays.fill(a, 0);
        }
        // i->i+1, j->j+1
        for (int i = 0; i < t1.length(); i++) {
            for (int j = 0; j < t2.length(); j++) {
                if (t1.charAt(i) == t2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else {
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
                }
            }
        }
        return dp[t1.length()][t2.length()];
    }

    public int longestCommonSubsequence2(String text1, String text2) {
        // dp[i][j] 表示到 (i, j)为止的最长子序列长度
        // 注意不一定以 i，j 结尾
        int[][] dp = new int[text1.length()][];

        for (int i = 0; i < text1.length() ; i++) {
            dp[i] = new int[text2.length()];
        }

        dp[0][0] = (text1.charAt(0) == text2.charAt(0)) ? 1 : 0;
        for (int j = 1; j < text2.length(); j++) {
            dp[0][j] = 0;
            if (dp[0][j-1] == 1 || text1.charAt(0) == text2.charAt(j)) {
                dp[0][j] = 1;
            }
        }

        for (int i = 1; i < text1.length() ; i++) {
            dp[i][0] = 0;
            if (dp[i-1][0] == 1 || text1.charAt(i) == text2.charAt(0)) {
                dp[i][0] = 1;
            }
        }

        for (int i = 1; i < text1.length() ; i++) {
            for (int j = 1; j < text2.length(); j++) {
                int temp = 0;
                if (text1.charAt(i) == text2.charAt(j)) {
                    temp = dp[i-1][j-1] + 1;
                }
                dp[i][j] = Math.max(Math.max(dp[i-1][j], dp[i][j-1]), temp);
            }
        }
        return dp[text1.length()-1][text2.length()-1];
    }
}
